1. Field of the Invention
The present invention relates generally to associative data storage and retrieval as, for example, in content addressable memory ("CAM") devices. More particularly, the invention relates to a CAM search mode of operation, and more specifically to a method and apparatus for a CAM circuit having self-timing functionality.
2. Description of Related Art
Random access memory ("RAM") is perhaps the most common form of integrated circuit memory available in the state of the art. However, RAM devices are not suited for use in systems which process associative data. The well known methodology of sequentially accessing data when reading from the RAM, where the data address is input and the data itself stored at the address is output, is inefficient for systems involving stored information involving pattern recognition, data compression, natural language recognition, sparse matrix processes, data-base interrogation, and the like, since the address associated with the desired stored data may not be known. For this type of data, it is more efficient to interrogate a memory by supplying a compressed subset of the desired data or a code representative of the full data set. The memory responds by indicating either the presence or absence of the desired data set and, if a match occurs, the respective address in the memory bank for that data set.
In the 1980's, another type of integrated circuit memory device was developed to have ambiguous, non-contiguous addressing and was dubbed the content addressable memory ("CAM"). See e.g., U.S. Pat. No. 3,701,980 (Mundy). In essence, for this type of associative data storage, the entire CAM can be searched in a single clock cycle, giving it a great advantage over the sequential search technique required when using a RAM device.
For example, a data string dictionary can be stored in a CAM and used in generating Lev-Zempel compressed output data (known in the art as "LZ," generically used for any LZ data compression technique; see "Compression of Individual Sequences Via Variable-Rate Coding", IEEE Transactions on Information Theory, 24(5):530-536, September 1978). The input data signal to the CAM would comprise a bit string representation of the data which is being searched for in the CAM. The output would be a signal indicative as to whether the data was found, e.g., a MATCH signal, and, if found, the location within the CAM array of memory cells, also referred to as the cam core, e.g., a MATCH.sub.-- ADDRESS signal. Obtaining this MATCH and MATCH.sub.-- ADDRESS information is done with a "match encoder."
The problem with CAM devices is that compared to RAM each individual cell structure is relatively complex. See e.g., U.S. Pat. No. 4,780,845 (Threewitt); incorporated herein by reference. Thus, for the same integrated circuit real estate, a CAM device can not match the density, speed, or low-power performance of a RAM device. Integrated circuit fabrication process improvements generally affect both types of devices equally, so that in relative terms, CAM architects can not do much to narrow the performance gap.
Many signals in the CAM are signals which will only transition in one direction between the start of a search cycle and the output of the MATCH and MATCH.sub.-- ADDRESS. The time after the MATCH.sub.-- ADDRESS is output and before the next CAM search is started must include returning the CAM cells to a pre-search state, referred to as "precharge time." For example, during precharge time, all output logic of the CAM is driven to a HIGH state, ready to be driven to its NO.sub.-- MATCH state, a HIGH to LOW transition, in one direction during a search. If a search is initiated and completed in one clock period, the precharge time must be less than or equal to half the cycle. For example, in a 15-nanosecond ("ns") system clock period, the precharge has to be completed in less than 7.5 ns. Depending on CAM size, combinatorial input logic timing, and the like as would be known to a person skilled in the art, the CAM precharge setup allotment of time may even be much less.
Therefore, there is a need for a self-timed precharge method and apparatus for CAM devices.